home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6551 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.6 KB
  1. Path: info.ucla.edu!agate!kaskel
  2. From: kaskel@kirkuk.berkeley.edu (Bruce Kaskel)
  3. Newsgroups: sci.math,comp.programming,comp.lang.c
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 19 Feb 1996 11:00:05 GMT
  6. Organization: U.C. Berkeley Math. Department.
  7. Message-ID: <4g9l7l$9br@agate.berkeley.edu>
  8. References: <DMy5wC.HoL@cwi.nl> <mjs.824400445@hubcap> <4g48sg$ljq@agate.berkeley.edu> <1996Feb19.051528.14105@news.etc.bc.ca>
  9. NNTP-Posting-Host: kirkuk.berkeley.edu
  10.  
  11. In article <1996Feb19.051528.14105@news.etc.bc.ca>,
  12. Robert Morewood <rmorewoo@cln.etc.bc.ca> wrote:
  13. >
  14. >The problem was to find the last non-zero digit of a large factorial.
  15. >(For example 1000!)
  16. [snip]
  17. >I solved did the 1000! problem quite easily on paper using a recursive 
  18. >approach based on the observation that:
  19. >{ Product mod 10 of odd numbers not divisible by 5 less than or equal to N
  20. >{ depends only on N MOD 20.  (Since 1*3*7*9*11*13*17*19 = 1 Mod 10.)
  21.  
  22. Very nice! Here is a C-implemenation of your recursive algorithm. 
  23.  
  24. I figure it should be about 100 times faster for 1000! than the looping 
  25. methods.
  26.  
  27. --Bruce
  28. ============================================================================
  29.  
  30. int a[20]={1,1,1,3,3,3,3,1,1,9,9,9,9,7,7,7,7,9,9,1};
  31. int b[4]={6,2,4,8};
  32.  
  33. int rightmost_nonzero_digit(n)
  34. int n;
  35. {
  36. int u,t;
  37. if(n<2) return(1);
  38. foo(n,&u,&t);return((u*b[t])%10);
  39. }
  40.  
  41. int foo(n,x,y)
  42. int n,*x,*y;
  43. {
  44. int i=1,j=0,m=n>>1,u,f;
  45. odds(n,&u,&f);
  46. if (m>1) foo(m,&i,&j);
  47. *x=(u*i)%10;*y=(m+(4-f)+j)&3;
  48. }
  49.  
  50. int odds(n,x,f)
  51. int n,*x,*f;
  52. {
  53. int q=1,r=0,s=n/5;
  54. if(s>2) odds(s,&q,&r);
  55. *x=(q*a[n%20])%10;
  56. *f=(r+((s+1)>>1))&3;
  57. return;
  58. }
  59.  
  60.  
  61.  
  62.